package previous.Test_0211;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //目标和
    int s;
    int sum;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums,target,0);
        return s;
    }
    public void dfs(int[] nums,int target,int pos){
        //方法添加
        if(pos==nums.length ){
            if(sum==target)
            s++;
            return;
        }
        //加法
        sum+=nums[pos];
        dfs(nums,target,pos+1);
        //恢复
        sum-=nums[pos];
        //减法
        sum-=nums[pos];
        dfs(nums,target,pos+1);
        //恢复
        sum+=nums[pos];
    }
    //组合总和
    List<List<Integer>> ret;
    List<Integer> path;
    int pos;
    int aim;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
          ret=new ArrayList<>();
          path=new ArrayList<>();
          aim=target;
         dfs1(candidates,0,0);
          return ret;
    }
    public void dfs1(int[] nums,int pos,int sum1){
        //添加
        if(sum1==aim){
            ret.add(new ArrayList<>(path));
            return ;
        }
        //出口
        if(pos==nums.length || sum1>aim){
            return ;
        }
        for (int i = pos; i < nums.length; i++) {

            sum1+=nums[i];
            path.add(nums[i]);
            dfs1(nums,i,sum1);
            //恢复
            sum1-=nums[i];
            path.remove(path.size()-1);}
        }

    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        ret=new ArrayList<>();
        path=new ArrayList<>();
        aim=target;
        dfs2(candidates,0,0);
        return ret;
    }
    public void dfs2(int[] nums,int pos,int sum1){
        //添加
        if(sum1==aim){
            ret.add(new ArrayList<>(path));
            return ;
        }
        //出口
        if(pos==nums.length || sum1>aim){
            return ;
        }
        for (int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs2(nums,i,sum1+nums[i]);
            path.remove(path.size()-1);}
    }
    //字母大小全排列
    List<String> ret1;
    StringBuilder path1;
    public List<String> letterCasePermutation(String s) {
        ret1=new ArrayList<>();
        path1=new StringBuilder();
        dfs3(s,0);
        return ret1;
    }
    public void dfs3(String s,int pos){
        //出口
        if(s.length()==pos){
            ret1.add(path1.toString());
            return;
        }
        //逐个遍历，不是从头遍历数组，不用for循环语句
        //不改变
        char ch=s.charAt(pos);
        path1.append(ch);
        dfs3(s,pos+1);
        path1. deleteCharAt(path1.length()-1);
        //改变
         if(ch>='a' && ch<='z' || ch>='A' && ch<='Z'){
         if(ch>='a' && ch<='z'){
                   ch-=32;
               } else{
                   ch+=32;
               }
        path1.append(ch);
             dfs3(s,pos+1);
              path1. deleteCharAt(path1.length()-1);
        }
    }
    //优美的排列
    int sum2;
    boolean[] check;
    public int countArrangement(int n) {
        int[] nums=new int[n];
        check=new boolean[n+1];
        dfs4(n,1);
        return sum2;
    }
    public void dfs4(int n,int pos){
        //出口
        if(pos==n+1){
            sum2++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            //合法
            if(check[i]==false && (pos%i==0||i%pos==0)){
                check[i]=true;
                dfs4(n,pos+1);
                check[i]=false;
            }
        }
    }

    }

